package com.yuw.fun;

import java.util.Scanner;

public class Test03 {

	public static void main(String[] args) {
		getF();
	}

	/**
	 * 从控制台输入求解的项数，并求解第n项的值
	 */
	private static void getF() {
		System.out.println("请输入所要求的的斐波那契数列的第几项：");
		Scanner sc = new Scanner(System.in);
		// 获取所有的项数
		int n = sc.nextInt();
		// 计算性能——获取当前时间的毫秒数
		long lBegin = System.currentTimeMillis();
		// 调用斐波那数列求解的递归函数
		// long lResult = caculateF(n);
		long lResult = caculateFF(n);
		// 执行结束之后，获取当时的毫秒数
		long lEnd = System.currentTimeMillis();
		// 计算程序所耗费的时间
		System.out.println("程序运行所花费的时间为：" + (lEnd - lBegin) + "毫秒");
		System.out.println("斐波那契数列的第" + n + "项的值为：" + lResult);
	}

	/**
	 * 递归求解斐波那契数列的第N项的值
	 * 
	 * @param n
	 *            第n项
	 * @return 第n项的值
	 */
	private static long caculateF(int n) {
		// （1）递归结束条件
		if (n == 1 || n == 2) {
			return 1;
		}
		// （2）递归调用
		return caculateF(n - 2) + caculateF(n - 1);
	}

	/**
	 * 非递归求解斐波那契数列第N项的值
	 * 
	 * @param n
	 *            第几项
	 * @return 第N项的值
	 */
	private static long caculateFF(int n) {
		// 返回值变量
		long lReault;
		// 前一项的值（第一项的值）
		long param1 = 1;
		// 后一项的值（第二项的值）
		long param2 = 1;
		// 第一项和第二项直接取值1
		if (n == 1 || n == 2) {
			lReault = 1;
		} else {
			for (int i = 1; i <= n - 2; i++) {
				// 从第三项开始，是前两项之和
				// long temp = param2; // 保留旧的param2的值
				param2 = param1 + param2; // 计算后一项是前两项之和
				param1 = param2 - param1; // 把旧的param2的值赋值给param1
				// param1 = temp;// 把旧的param2的值赋值给param1
			}
			// param2的值就是第N项的值
			lReault = param2;
		}
		return lReault;
	}

}
